import collections
from typing import List


class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        m, n = len(forest), len(forest[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        def get_distance(x1, y1, x2, y2):
            """(x1,y1)与(x2,y2)之间的距离"""
            visited = {(x1, y1)}
            queue = collections.deque([(x1, y1)])
            d = 0
            while queue:
                for _ in range(len(queue)):
                    x3, y3 = queue.popleft()
                    if (x3, y3) == (x2, y2):
                        return d
                    for (x4, y4) in neighbors(x3, y3):
                        if forest[x4][y4] != 0 and (x4, y4) not in visited:
                            visited.add((x4, y4))
                            queue.append((x4, y4))
                d += 1
            return -1

        # 统计数目总数
        # 统计最低的树
        tree_num = 0
        tree_lst = []
        for i in range(m):
            for j in range(n):
                if forest[i][j] > 1:
                    tree_num += 1
                    tree_lst.append((i, j))
        tree_lst.sort(key=lambda x: forest[x[0]][x[1]])

        ans = 0  # 当前移动步数
        i1, j1 = 0, 0  # 当前位置
        now = 0  # 当前准备需要砍的树的坐标
        while now < tree_num:
            i2, j2 = tree_lst[now]
            distance = get_distance(i1, j1, i2, j2)
            if distance == -1:
                return -1
            ans += distance
            i1, j1 = i2, j2
            now += 1
        return ans


if __name__ == "__main__":
    # 6
    print(Solution().cutOffTree([
        [1, 2, 3],
        [0, 0, 4],
        [7, 6, 5]
    ]))

    # -1
    print(Solution().cutOffTree([
        [1, 2, 3],
        [0, 0, 0],
        [7, 6, 5]
    ]))

    # 6
    print(Solution().cutOffTree([
        [2, 3, 4],
        [0, 0, 5],
        [8, 7, 6]
    ]))
